package alg2_bagQueueStack;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

import java.util.Iterator;

//使用链表实现栈
public class Test2_StackWithLink<Item> implements Iterable<Item> {

    public static void main(String[] args) {
        Test2_StackWithLink stackWithLink = new Test2_StackWithLink();

        while (!StdIn.isEmpty()){
            String item = StdIn.readString();
            if (!item.equals("-")){
                stackWithLink.push(item);
            }else if(!stackWithLink.isEmpty()){
                StdOut.print(stackWithLink.pop() + "");
            }
        }
        StdOut.println("(" + stackWithLink.size() + " left on stack)");
    }

    private Node first;//栈顶
    private int N;//元素数量

    //定义了节点的嵌套类
    private class Node {
        Item item;
        Node next;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public int size() {
        return N;
    }

    //向栈顶添加元素
    public void push(Item item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }

    //从栈顶删除元素
    public Item pop() {
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }

    @Override
    public Iterator<Item> iterator() {
        return null;
    }

}
